package graph;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.*;


/**
 * @data 2021/10/xx
 * 对图对一个实现  经典呀！
 */
@NoArgsConstructor
@Data
public class GraphArray {
    public static void main(String[] args) {
        String vertexArray[] = {"A", "B", "C", "D", "E", "F", "G", "H"};
        GraphArray graph = new GraphArray(vertexArray.length);
        // 把节点添加到图中
        for (String s : vertexArray) {
            graph.insertVertex(s);
        }
        graph.insertEdge("A", "B", 1);
        graph.insertEdge("A", "C", 1);
        graph.insertEdge("B", "E", 1);
        graph.insertEdge("B", "D", 1);
        graph.insertEdge("C", "F", 1);
        graph.insertEdge("C", "G", 1);
        graph.insertEdge("F", "G", 1);
        graph.insertEdge("D", "H", 1);
        graph.insertEdge("H", "E", 1);
        graph.display();
        graph.dfs();
        System.out.println("使用broad first search");
        graph.bfsV2();
    }

    // 存储顶点集合
    private ArrayList<String> vertexList;
    // 二维数组
    private ArrayList<ArrayList<Integer>> edges;
    // 表示边的数目
    private int numOfEdges;
    // 顶点是否被访问 这个数组被二个方法使用着 分别为dfs and prim 注意
    private boolean[] isVisited;
    // 顶点是否被添加进队列、
    private boolean[] isAdded;
    // bfs 需要一个队列
    ArrayDeque deque;


    public GraphArray(int n) {
        // 对二维数组和顶点集合初始化
        edges = new ArrayList<>(n);
        // 有点坑的一点就是arrayList与数组不会初始化数组为0 这里需要我们手动分配
        for (int i = 0; i < n; i++) {
            ArrayList temp = new ArrayList();
            for (int j = 0; j < n; j++) {
                temp.add(0);
            }
            edges.add(temp);
        }
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
        isVisited = new boolean[n];
        isAdded = new boolean[n];
        deque = new ArrayDeque();

    }

    // 插入顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }
    // 插入边

    /**
     * v1 表示顶点集合Array下标 weight表示v1和v2之间是否有关系 用1 and 0
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges.get(v1).set(v2, weight);
        edges.get(v2).set(v1, weight);
        numOfEdges++;
    }

    /**
     * 重写了一下insert方法，我们可以之间插入顶点 方便查看
     */
    public void insertEdge(String v1, String v2, int weight) {
        int e1 = vertexList.indexOf(v1);
        int e2 = vertexList.indexOf(v2);
        edges.get(e1).set(e2, weight);
        edges.get(e2).set(e1, weight);
        numOfEdges++;
    }


    // 获取图节点的个数
    public int getVertexSize() {
        return vertexList.size();
    }

    // 获取图边的条数
    public int getNumOfEdges() {
        return this.numOfEdges;
    }

    // 通过结点下标获取结点名字
    public String getNodeNameByIndex(int i) {
        return vertexList.get(i);
    }

    // 返回v1和v2的权值
    public int getWeight(int v1, int v2) {
        return edges.get(v1).get(v2);
    }

    public void display() {
        edges.stream().forEach(System.out::println);
    }

    // 通过传入的index获得
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges.get(index).get(i) != 0) {
                return i;
            }
        }
        return -1;
    }

    // 获得邻结点下标
    public int getNextNeighbor(int i, int j) {
        for (int k = j + 1; k < vertexList.size(); k++) {
            if (edges.get(i).get(k) != 0) {
                return k;
            }
        }
        return -1;
    }

    /**
     * 十分简洁的dfs
     *
     * @param i
     */
    public void dfs(int i) {
        System.out.println(getNodeNameByIndex(i));
        isVisited[i] = true;
        /**
         * 很重要的代码  w!=-1 表明没有与他相连的结点了
         *             for循环的结束表明遍历完了
         */
        for (int w = getFirstNeighbor(i); w != -1; w = getNextNeighbor(i, w)) {
            if (!isVisited[w]) {
                dfs(w);
            }
        }
    }

    /**
     * 这种情况也是因为存在非连通的情况
     */
    public void dfs() {
        for (int i = 0; i < vertexList.size(); i++) {
            if (isVisited[i] == false) {
                dfs(i);
            }
        }
    }

    /**
     * bfs breadth first search 使用了递归 这代码太垃圾了 自己写的
     */
    public void bfs(int i) {
        System.out.println(getNodeNameByIndex(i));
        if (i == 0) {
            isAdded[i] = true;
            deque.add(i);
        }
        if (!deque.isEmpty()) {
            int j = (int) deque.pop();
            for (int l = getFirstNeighbor(j); l != -1; l = getNextNeighbor(i, l)) {
                if (!isAdded[l]) {
                    deque.add(l);
                    isAdded[l] = true;
                }
            }
        }
        if (!deque.isEmpty()) {
            bfs((Integer) deque.peek());
        }
    }

    /**
     * bfs 不使用递归 参考了老师的代码 将变量声明提到循环或者递归以外 节约内存
     * 可能会有非连通图的情况 对这个方法进行一个重载
     */
    public void bfsV2(int i) {
        int u;// 表示队列头节点对应的下标
        int w; // 表示邻结点下标
        System.out.println(getNodeNameByIndex(i));
        deque.add(i);
        isAdded[i] = true;
        while (!deque.isEmpty()) {
            // 取出队列头
            u = (int) deque.pop();// 获取邻结点
            for (w = getFirstNeighbor(u); w != -1; w = getNextNeighbor(u, w)) {
                // 未被加入队列
                if (isAdded[w] == false) {
                    System.out.println(getNodeNameByIndex(w));
                    isAdded[w] = true;
                    deque.add(w);
                }
            }
        }
    }

    /**
     * 可能会有非连通结点的情况 所以我们需要遍历
     */
    public void bfsV2() {
        for (int i = 0; i < vertexList.size(); i++) {
            if (isAdded[i] == false) {
                bfsV2(i);
            }
        }
    }

    /**
     * 编写prim算法
     * i 表示从那个顶点开始  prim算法针对 已连通顶点的集合 与没访问顶点的距离
     */
    public void prim(int v) {
        int u = 0; // 表示row下标
        int w = 0;  // 表示col下标
        int minWeight = 10000;
        isVisited[v] = true;
        // 最外面的循环控制次数  n个顶点 n-1次计算得到n-1条边
        for (int counts = 1; counts < vertexList.size(); counts++) {
            // i指已经被访问过的节点  j表示没有被访问过的节点  这样就可以遍历得到未访问过的节点到已经访问过节点集合最短距离
            // 换句话说这个是确定每一次生成的子图，和那个的距离最近
            for (int i = 0; i < edges.size(); i++) {
                if (isVisited[i] == true) { // 小优化 减少循环次数
                    for (int j = 0; j < edges.get(0).size(); j++) {
                        if (edges.get(i).get(j) != 0 && isVisited[i] == true && isVisited[j] == false && edges.get(i).get(j) < minWeight) {
                            u = i;
                            w = j;
                            minWeight = edges.get(i).get(j);
                        }
                    }
                }
            }
            isVisited[w] = true;
            minWeight = 10000;
            System.out.println(getNodeNameByIndex(u) + "->" + getNodeNameByIndex(w) + edges.get(u).get(w));
        }
    }

    /**
     * 、
     * 10/06
     * 应用场景 最短路径
     * kruskal算法核心是避免成环，方法是并查集 最大作用是检查一个图上面是否形成了环
     */
    public void kruskal(int v) {
        // 获取图中所有边的集合  10条
        EData[] eData = getEdges();
        Arrays.sort(eData);
        int[] parent = new int[vertexList.size()]; // 用于保存节点终点
        int[] rank = new int[vertexList.size()];  // 用于保存树的高度
        initialise(parent);
        //遍历eData
        for (int i = 0; i < eData.length; i++) {
            int x = eData[i].getStart();
            int y = eData[i].getEnd();
            if (unionVertices(x, y, parent, rank) == true) {
                System.out.println(getNodeNameByIndex(x) + "->" + getNodeNameByIndex(y) + "  " + eData[i].getWeight());
            }
        }
    }

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    class EData implements Comparable<EData> {
        int start;
        int end;
        int weight;

        @Override
        public int compareTo(EData o) {
            return this.weight - o.weight;
        }
    }

    /**
     * 将二维数组里面权重找出来，放到类中
     */
    private EData[] getEdges() {
        int index = 0;
        EData[] eData = new EData[getNumOfEdges()];
        for (int i = 0; i < vertexList.size(); i++) {
            // 这个+1 nb 遍历上三角
            for (int j = i + 1; j < vertexList.size(); j++) {
                if (edges.get(i).get(j) != 0) {
                    eData[index++] = new EData(i, j, edges.get(i).get(j));
                }
            }
        }
        return eData;
    }

    /**
     * 初始化 默认为-1
     *
     * @param parent
     */
    public void initialise(int parent[]) {
        for (int i = 0; i < vertexList.size(); i++) {
            parent[i] = -1;
        }
    }

    /**
     * 并查集数组，用来获取终点的下标
     * 很精妙 如果我有父节点，返回父节点，如果没有（孤儿节点）那么返回我自己
     * 其中xRoot是某线段起点的根节点，yRoot是同样某线段终点的根节点。
     */
    public static int getRoot(int i, int[] ends) {
        while (ends[i] != -1) {
            i = ends[i];
        }
        return i;
    }

    /**
     * 其中xRoot是某线段起点的根节点，yRoot是同样某线段终点的根节点。
     */
    public static boolean unionVertices(int x, int y, int[] parent, int[] rank) {
        int xRoot = getRoot(x, parent);
        int yRoot = getRoot(y, parent);
        if (xRoot == yRoot) {
            return false;
        } else {
            if (rank[x] > rank[y]) {
                parent[yRoot] = xRoot;
            } else if (rank[x] < rank[y]) {
                parent[xRoot] = yRoot;
            } else {
                // 此时二树的高度相等 我们让x成为y的儿子
                parent[xRoot] = yRoot;
                rank[yRoot]++;
            }

        }
        return true;
    }

    /**
     * 2021/10/07
     * Dijkstra最短路径算法 用于计算一个顶点到另外一个顶点到最短路径
     * 主要特点是以起始点为中心向外层扩散（bfs）直到扩展到终点为止  bfs + greedy
     * 可以结合演示动画：https://www.bilibili.com/video/BV1zz4y1m7Nq?from=search&seid=3192131596331347464&spm_id_from=333.337.0.0
     * 我从v点寻找到了到其他顶点最小到距离
     */
    public void dijkstra(int v) {
        // 需要二个数组
        int distance[] = new int[vertexList.size()];
        for (int i = 0; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        distance[v] = 0;
        int preNode[] = new int[vertexList.size()];
        preNode[v] = -1;
        isVisited[v] = true;
        int minWeight = Integer.MAX_VALUE;
        // 控制循环次数
        for (int k = 1; k < vertexList.size(); k++) {
            // bfs + 将bfs遍历到的点距离加上权值
            for (int w = getFirstNeighbor(v); w != -1; w = getNextNeighbor(v, w)) {
                if (isVisited[w] == false) {
                    int dis = edges.get(v).get(w) + distance[v];
                    if (dis < distance[w]) {
                        distance[w] = dis;
                        preNode[w] = v;
                    }
                }
            }
            // 在distance数组中寻找最小值 && 没有访问过的节点，作为下一个开始bfs的点
            int nextV = 0;
            for (int i = 0; i < vertexList.size(); i++) {
                if (isVisited[i] == false && minWeight > distance[i]) {
                    nextV = i;
                }
            }
            isVisited[nextV] = true;
            v = nextV;
            minWeight = Integer.MAX_VALUE;
        }
        // 打印语句
        for (int i = 0; i < preNode.length; i++) {
            int temp = i;
            while (temp != -1) {
                System.out.printf(temp + ",");
                temp = preNode[temp];
            }
            System.out.println("权值路径为" + distance[i]);
        }
        System.out.println(Arrays.toString(preNode));
        System.out.println(Arrays.toString(distance));
        System.out.println(Arrays.toString(isVisited));
    }

    /**
     * floyd 用于一个顶点到剩余顶点到最短路径，但是"一个顶点"是图中的所有顶点
     */
    public void floyd(){
        int i ,j ,v;
        // 初始化路径数组
        int path[][] = new int[vertexList.size()][vertexList.size()];
        for (int k = 0; k < path.length; k++) {
            for (int l = 0; l < path[0].length; l++) {
                path[k][l] = -1;
            }
        }
        for (int k = 0; k < edges.size(); k++) {
            for (int l = 0; l < edges.get(0).size(); l++) {
                if (k!=l && edges.get(k).get(l)==0){
                    edges.get(k).set(l,100000);
                }
            }
        }
        System.out.println("init");
        for (ArrayList<Integer> edge : edges) {
            System.out.println(edge);
        }
        /**
         * 核心代码
         * 不想做无谓到解释，结合上述演示动画
         * i：中间点 所有顶点
         * j 和 v 选出所有的顶点对
         */
        for ( i = 0; i < vertexList.size(); i++) {
            for ( j = 0; j <vertexList.size() ; j++) {
                for ( v = 0;v<vertexList.size(); v++) {
                    if (i!=j && i!=v && j!=v){  //第三边大于二边之和   所以三个边的顶点不能重合
                        if (edges.get(j).get(v) > edges.get(j).get(i)+edges.get(i).get(v)){
                            edges.get(j).set(v,edges.get(i).get(j)+edges.get(i).get(v));
                            path[j][v] = i;
                        }
                    }
                }
            }
        }
        System.out.println("init");
        for (ArrayList<Integer> edge : edges) {
            System.out.println(edge);
        }
        System.out.println("path数组");
        for (int k = 0; k <path.length ; k++) {
            for (int l = 0; l <path[0].length ; l++) {
                printPath(k,l,path);
                System.out.printf("权值为"+edges.get(k).get(l));
                System.out.println();
            }
        }
    }
    /**
     * 递归输出path数组  哇好巧妙到递归啊！
     */
    public void printPath(int u,int v,int path[][]){
        if (path[u][v]==-1){
            System.out.print(u+"到"+v+",");
        }else {
            int mid = path[u][v];
            printPath(u,mid,path);
            printPath(mid,v,path);
        }

    }
}
